COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	bird[e82,jmc]		Minsky's bird example - for circumscription
C00022 00003	We shall refer to the conjunction of the above as
C00028 00004	Abstract:
C00030 ENDMK
C⊗;
bird[e82,jmc]		Minsky's bird example - for circumscription

A BIRD CAN FLY - UNLESS IT CAN'T

	In his 1982 August presidential address to the American Association for
Artificial Intelligence, Marvin Minsky again
expressed his doubts about the suitability of mathematical logical
languages for representing facts about the common sense world.  He
cited the well known example of non-monotonic reasoning involved in
inferring the conclusion that if Tweety is a bird then Tweety can
fly while remaining prepared to acknowledge exceptions such as ostriches,
penguins, dead birds, birds with casts on their wings, and remaining open
to still others that no-one has yet proposed.

	If the only means of reasoning proposed is logical deduction,
it seems impossible to express the known common sense facts
about the ability of birds to fly.  The problem is that the simple axiom

	∀x.bird x ⊃ canfly x

admits exceptions and requires qualification.  If we qualify it by writing

	∀x. bird x ∧ ¬ostrich x ⊃ canfly x,

we are immediately invited to add more qualifications including some
that no-one has ever heard of before.  Since no-one has heard of them
before, it is implausible that they can be part of every human's
common sense knowledge.  This "qualification problem", discussed in
(McCarthy 1977) is one of the motivations for introducing
formalized non-monotonic reasoning.

	Various authors have proposed to save the use of logical languages,
which have the many virtues recounted in
(McCarthy 1960), (McCarthy and Hayes 1969), (Hayes 197x), Nilsson (1981) and
 (Newell 1980),
by supplementing logical deduction by various
kinds of formalized non-monotonic reasoning.  One such proposal, called
circumscription, is described in (McCarthy 1980), and the object of this
note is to express the common sense knowledge about the ability of birds
to fly as a first order axiom and to show how circumscription may be used
to draw the conclusions expected from commons sense and not others.  Thus
we propose to meet one of the challenges expressed in Minsky's address.

	The basic idea is to use an axiom

	∀x.bird x ∧ ¬prevfly x ⊃ canfly x

where  prevfly  is a new predicate such that  prevfly x  asserts that
x  is prevented from flying.  If we only allowed deductive reasoning,
prevfly  wouldn't help, because its use would amount merely to asserting
that a bird can fly unless it can't.  However, we use circumscription to
infer that a bird is not prevented from flying unless there is information
permitting the inference that it is prevented.  This amounts to asserting
that  prevfly  has the minimal extension compatible with the facts about
it that we take into account.

	We work with the following set of axioms as representing the
relevant part of a hypothetical data base of common sense knowledge.
The reader should consider whether he accepts these assertions as expressing
general common sense knowledge and not ad hoc to a particular problem.

1. ∀x.bird x  ∧ ¬prevfly x ⊃ canfly x

2. ∀x.penguin x ⊃ bird x
   ∀x.ostrich x ⊃ bird x
   ∀x.canary x ⊃ bird x

3. ∀x.ostrich x ⊃ prevfly x
   ∀x.penguin x ⊃ prevfly x
   ∀x.dead x ⊃ prevfly x

	The point of the qualification problem is that there can be
any number of facts like those listed under 3.  When a new one is remembered
or discovered or conjectured, it can be added to the above list.
Through the magic of circumscription, such a new fact will interfere with
our concluding that Tweety can fly only if there is positive evidence that
the new circumstance applies to Tweety.

4. ostrich Joe
   canary Tweety
   rock Henry

5. ∀x.prevfly x ⊃ ¬canfly x	; this one is unnecessary to do this
				; problem but may help with other problems.


	We shall begin by presenting the circumscriptive reasoning so as
to reach our goals.  In particular, we choose the order of circumscription
and what facts are taken into account.  After that we will discuss what
would cause an unprejudiced person or program to do circumscriptions in a
suitable order.


Goals:

	The ground facts we wish to come up with are:

	bird Tweety	; follows deductively
	bird Joe	; follows deductively
	¬bird Henry	; will require a circumscription minimizing  bird

	prevfly Joe	; Not actually used except in connection with 5
			; to show positively that Joe can't fly.

	¬prevfly Tweety; This requires circumscribing  prevfly and addtional
			; circumscriptions to show that Tweety isn't Joe
			; or any other ostrich.

	canfly Tweety	; Our main goal

	¬canfly Joe	; A purely deductive conclusion.  Since we can imagine
			; that ostriches might fly in sufficiently low gravity
			; and sufficiently high air density, there really should
			; be another potentially disabling predicate in
			; axiom 3, so that the part about ostriches would
			; become

3'. ∀x.ostrich x ∧ ¬prevprevfly x ⊃ prevfly x

If we are taking into account no facts that might enable one to deduce
that an ostrich can fly after all, circumscribing  prevprevfly  will
make it always false, and axiom  3'  will reduce to axiom 3.
In what follows we will use  3  rather than  3'.


Reasoning:

	There are several circumscriptions we could do.  The simplest
would be to circumscribe  prevfly  in the conjunction of the axioms  3.
The circumscription schema is then

[∀x.ostrich x ⊃ P x] ∧ [∀x.penguin x ⊃ P x] ∧ [∀x.dead x ⊃ P x] ∧ [∀x.Px ⊃ prevfly x]
	⊃ [∀x.prevfly x ⊃ Px]

where  P  is the predicate variable of the schema.  Setting

	P x ≡ ostrich x ∨ penguin x ∨ dead x

makes each of the four conjuncts of the left side of the schema satisfied,
and so we get

∀x.prevfly x ⊃ ostrich x ∨ penguin x ∨ dead x.

Combining this with  3  gives

∀x. prevfly x ≡ ostrich x ∨ penguin x ∨ dead x,

asserting that exactly ostriches, penguins and the dead are prevented from
flying.  This is the result we want, considering that we are taking into
account only those obstacles to flying,
 but what justifies taking only  3
into account and leaving  1  and  5  out of the circumscription?

	Actually including  5  in the circumscription presents no problem.  We
get an extra premiss

	∀x.P x ⊃ ¬ canfly x

in the circumscription schema, and when we substitute for   P x  the disjunction
mentioned above, this becomes

	∀x.ostrich x ∨ penguin x ∨ dead x ⊃ ¬canfly x

which is provable from  3  and  5.

	However, including  1  in the circumscription would leave us with

	∀x.prevfly x ≡ ostrich x ∨ penguin x ∨ dead x ∨ (bird x ∧ ¬canfly x),

and the last term makes this unusable.

	There is another way to get the desired answer and still include
1 in the circumscription formula.  Namely, we include  1  but regard
canfly  as a variable that can be chosen so as to minimize  prevfly.
The circumscription schema then becomes.

[∀x.bird x ∧ ¬P(x) ⊃ Q x] ∧ [∀x.ostrich x ⊃ P x] ∧ [∀x.penguin x ⊃ P x]
∧ [∀x.dead x ⊃ P x] ∧ [∀x.P x ⊃ prevfly x]
		⊃ ∀x.prevfly x ⊃ P x.

Now we can choose  P  as before and choose  Q  so as to make the first
premiss true.

	We regard this alternative as better than only including  3  in
the circumscription, because we then take all available facts into account.
Moreover, if we had an additional fact  ¬canfly(Tom), then the premiss of
the circumscription would have the additional fact  ¬Q(Tom),  and
we would have to write

	P x ≡ x = Tom ∨ ostrich x ∨ penguin x ∨ dead x

in order to satisfy the left side of the schema, and this takes into
account the fact that Tom can't fly without interfering with Tweety.

	Circumscription is a rule of conjecture, so logically we could
stop at this point with the conclusion that it allows us to make the
conjecture we want in the case of Tweety.  However, since we want computer
programs to come up with the right conjectures,  we need some rules
about what should be circumscribed and what predicates should be allowed
to flap in the circumscription.  We have our choice as to whether these
rules are imbedded in the reasoning program or are represented by some
kind of meta-sentences.  We can even do both.  The meta-sentences will
be wanted if we want to do meta-reasoning logically.

	We don't have a general proposal at this time.
Here, however is a scheme that handles the present case and some more.  We
replace  prefly x  by the more general  prevented(canfly, x) and write

1''. ∀x.bird x ∧ ¬prevented(canfly,x) ⊃ canfly x.

Here  prevented  is taken as a second order predicate symbol that
takes a predicate and its arguments as arguments.  3  then becomes

	3''. ∀x.ostrich x ⊃ prevented(canfly,x), etc.

Now we can have a general rule that  prevented  is to be circumscribed
on its individual variable with its predicate variable flapping.

	We could also let  ostrich,  penguin,  and  dead  flap, and take
the facts  2  and  4  involving them into the circumscription.  The
result would be that we could take

	∀x.P x ≡ x = Joe

in the circumscription schema, since the predicate variables replacing
penguin  and  dead  can be taken as always false.
The conclusion then becomes

	∀x.prevfly x ≡ x = Joe,

and substituting  Tweety  into  1  and using  2  and  4  gives

	¬(Tweety = Joe) ⊃ canfly Tweety.


The unique names hypothesis

	The unique names hypothesis (Reiter 197x) is another form of
non-monotonic reasoning that says that objects with different names are
presumed to be different unless they are provable to be identical.
We prefer to reach this conclusion by circumscription in the following
way.  We index the objects by integers writing

6. object(1) = Joe
   object(2) = Tweety
   object(3) = Henry.

We then write

	∀m n.m≠n ∧ ¬prevented(different,m,n) ⊃ object(m) ≠ object(n).

As described above, the predicate  prevented  is to be circumscribed
with respect to any facts we may have causing numbers to designate
objects that are the same.  We assume also that we have enough
arithmetic to be able to prove that the numbers are different -
or (by an attachment) we trust our computer to tell us that they are.
In the present case we will have no facts that allow us to conclude
that any pair of Joe, Tweety and Henry are equal, and so we'll conclude
that they are different.

	Notice that writing

6*. number(Joe) = 1
    number(Tweety) = 2
    number(Henry) = 3

would force Joe, Tweety and Henry to be different rather than making
it a non-monotonic conclusion.

	If we imagine the above reasoning to be carried out in complete
isolation from all other facts, then the conclusion that  Joe  and
Tweety  are the only birds (not deduced above but deducible by the
same methods) would be acceptable, but a more rugged reasoning
program should be able to admit the existence of other birds and
flying objects.  This suggests the use of some such predicate as
relevant(x,P1)  meaning that  x  is relevant to problem  P1  and
relativizing the formulas with respect to this predicate.  We haven't
yet figured out how this should be done.


References:


John McCarthy
Computer Science Department
Stanford University
Stanford, CA 94305
Arpanet: JMC@SU-AI

We shall refer to the conjunction of the above as

	Axioms1(bird,prevfly,canfly,penguin,ostrich,canary,dead,rock,Joe,Tweety)

or just as  Axioms1.  In doing the circumscriptions, we will need to
substitute predicate variables for some of the arguments.  In this
Axioms1(bird',canfly')  will abbreviate

	Axioms1(bird',prevfly,canfly',penguin,ostrich,canary,dead,rock,Joe,Tweety).

Here we consider  bird'  and  canfly'  as predicate variables over which
we can quantify.



	It looks like we can win in this case by circumscribing all of the
predicate symbols simultaneously.  There seeems to be a unique minimal
model of  Axioms1, and in this minimal model, all our goals are satisfied.
This suggests that the bird example is too simple to illustrate the
facts about circumscription.  It contains no function symbols, and all
the predicate symbols have just one argument.





Further Discussion:

	1. I haven't done what was promised in discussing order of
circumscription or what sets of facts and predicates are to be
minimized.  There seems to be no harm in minimizing them all at
once.

	Incidentally, my paper doesn't say how to minimize two
predicates.  For generality, suppose that the predicates  P  and  Q  range
over different domains with running variables  x  and  y   of different
sorts corresponding to the domains.

We have

Axioms(P0,Q0) ∧

{∀P Q.Axioms(P,Q) ∧ [∀x.P(x) ⊃ P0(x)] ∧ [∀y.Q(y) ⊃ Q0(y)]
			⊃ [∀x.P0(x) ⊃ P(x)] ∧ [∀y.Q0(y) ⊃ Q(y)]}.

	More than two predicates are handled by the obvious extension.

	2. It may be that we can circumscribe on all predicates
simultaneously (if this is really true), because the axioms are
essentially Horn in all the predicates.  It might be argued that
axioms describing the naive physics of the world are likely to
be Horn, because the world is essentially deterministic.  On the
other hand, axioms expressing a state of knowledge are more likely
to be non-Horn, because we observe only a part of the world and
thus must express what we know at least partially by disjunctions.
This suggests that the non-Horn axioms associated with a particular
state of knowledge will play a special role.

	3. In fact circumscribing predicates one at a time while
holding the others as parameters gives the same result as simultaneous
circumscription.  Moreover, the result of a circumscription is unaffected
by including in the axiom part of the circumscription axioms that
don't involve the predicate being circumscribed.  As a result of this
we can do the circumscriptions in the following order with
the following results.




	We first want to circumscribe  prevfly.  It appears
in the axioms

1. ∀x.bird x ∧ ¬prevfly x ⊃ canfly x

which can be written

1'. ∀x.bird x ∧ ¬canfly x ⊃ prevfly x,

and

3. ∀x.ostrich x ⊃ prevfly x
   ∀x.penguin x ⊃ prevfly x
   ∀x.dead x ⊃ prevfly x,

5. ∀x.prevfly x ⊃ ¬canfly x,

which can be written

5'. ¬prevfly x ∨ ¬canfly x.



	Therefore, we need to find a way of justifying letting the
predicate  canfly  "flap"  in the circumscription, i.e. letting it
be chosen so as to help minimize  prevfly.  Only when we can find
reasonable rules for circumscription that will do this, will we be
able to make programs that use circumscription.

	The following ideas is tentatively advanced for this.  Instead
of writing  1,  we write
Abstract:
	In his 1982 presidential address to the American Association
for Artificial Intelligence Marvin Minsky again expressed his
opinion that logic, including non-monotonic logic, wasn't a good
bet for expressing common sense knowledge and common sense reasoning.
He illustrated this with the example of the common sense facts
about birds being able to fly except for ostriches, dead birds
and whatever other possible exceptions which anyone might chance to
think of.

	The original purpose of this article was just
 to take up Minsky's challenge
on behalf of one method of non-monotonic reasoning - the
circumscription of (McCarthy 1980).   However, in order to do
the example properly, and I hope convincingly, it was necessary
to make certain improvements and generalizations in circumscription,
and therefore the content of this paper is technical as well
as methodological.

	Mainly, it is necessary to include in the knowledge
base some information about the order in which circumscriptions are
normally to be done.  This normal order may itself be subject to
exceptions, but we don't pursue this kind of meta-level reasoning
in this paper.